The present invention relates to a traffic shaper that controls bandwidth usage in a packet communication system, and to packet communication apparatus incorporating this traffic shaper, with particular attention to a packet networks employing the asynchronous transfer mode (ATM) protocol.
An ATM network transports information in fixed-length packets referred to as cells. Transport is by time-division multiplexing, with the cell as the basic: unit of multiplexing. As shown in FIG. 1, a cell consists of a header 2 and payload field 4. The transport of each cell is controlled by its header 2, which indicates the type of cell and where the cell is to be routed. The payload field 4 contains the payload information of the cell.
The multiplexing is asynchronous in that there are no fixed time-slot assignments on the network communication lines. Any cell can be placed in any available time slot. If necessary, idle (empty) cells are transmitted to fill unused time slots, so that each communication line carries a steady cellstream. Idle cells are identified as such in their headers. The headers of non-idle cells contain routing information consisting of a virtual path identifier (VPI) and virtual channel identifier (VCI), or a line identifier (Nc).
The cellstream on each communication line in a network may include various types of cell traffic, having different data rates, some of which may fluctuate. Traffic is controlled according to contracts that are negotiated when connections are set up. These traffic contracts allocate network bandwidth by specifying rates at which cells can be sent, and may specify other information such as priority. Each node in the network must shape its outgoing cell traffic so as to stay within these bandwidth allocations. The part of the node apparatus that performs this function is referred to as the traffic shaper. The purpose of traffic shaping is to prevent degradation of communication quality due to congestion at receiving nodes.
Two other functions of an ATM network node, performed in particular at nodes where cell traffic; exits the network, are to distribute the cellstream multiplexed onto a network communication line to several outgoing lines, and to convert the cells distributed to each of these lines to the format required for transmission on that line. This last function is referred to as framing. The part of the communication apparatus that performs the distribution and framing functions at a network node is referred to as the line distributor.
FIG. 2 illustrates the traffic shaper and line distributor roles in an ATM communication network 25, when data are sent from a transmitting terminal 30 to a receiving terminal 31. The network 25 includes a first ATM communication apparatus 32 (such as an ATM switch) to which the transmitting terminal 30 is connected, a second ATM communication apparatus 33 (such as another ATM switch) to which the receiving terminal 31 is connected, and a third ATM communication apparatus 34 (such as another ATM switch, or a cross-connect apparatus) coupled between the first and second apparatuses 32 and 33. The first and second apparatuses 32 and 33 are also connected to other terminals 35 and 36. Traffic shapers (S) in the three apparatuses 32, 33, and 34 control the rate and timing at which cells originating at the transmitting terminal 30 can depart from these apparatuses 32, 33, and 34. The line distributor (D) in the second apparatus 33 distributes and frames the outgoing cells.
A virtual connection exists between the transmitting terminal 30 and the receiving terminal 31 in FIG. 2, in that a specific virtual path and channel are assigned to this connection at each ATM communication apparatus 32, 33, and 34. Multiplexing enables each apparatus to serve a large number of connections simultaneously.
FIG. 3 is a block diagram of a conventional traffic shaper 400, comprising a cell screening unit 401, a header extraction unit 402, a write controller 403, a scheduling table 404, a read controller 405, and a cell buffer bank 410. The cell buffer bank 410 has a plurality of cell buffers 411, 412 . . . 41n, each of which operates as a first-in-first-out (FIFO) buffer. A different buffer is used for each connection. These components are linked by signal lines 450 . . . , 47n as indicated in the drawing.
Input cells 490 arriving on signal line 450 are sent to the cell screening unit 401, which decides from the header of each cell whether the cell is idle or not. Non-idle cells are passed to the header extraction unit 402 on signal line 451. The header extraction unit 402 extracts the cell header, reads the virtual path and channel identifiers (VPI/VCI), and passes these identifiers to the write controller 403 on signal line 452. From the VPI/VCI information, the write controller 403 identifies the connection to which the cell belongs, selects the FIFO cell buffer assigned to that connection, and sends a write command over the corresponding one of the signal lines 461 . . . , 46n, causing the cell to be stored in the corresponding FIFO cell buffer.
The scheduling table 404 contains information specifying the rate at which cells are to be read from each of the FIFO cell buffers 411 . . . , 41n. The rate is chosen so as to satisfy the conditions of the traffic contract for the corresponding connection, and corresponds to the bandwidth allocated to that connection. The read controller 405 schedules cell output according to this information, which it receives via signal line 453, and sends read commands to the FIFO cell buffers 411 . . . , 41n via signal lines 471 . . . , 47n at the appropriate rates, selecting one cell buffer at a time. The selected buffer places an output cell 491 on signal line 454. If the selected buffer is empty, an idle cell is output.
The bit length of the virtual path and channel identifiers (twenty-four or twenty-eight bits) enables millions of different connections to coexist at one node. When the number of connections becomes this large, however, the method of traffic shaping employed in this conventional traffic, shaper 400 encounters certain problems.
One problem is that a very large amount of buffer memory is required to provide a separate cell buffer for each connection. In practice, the number of connections supported by a traffic shaper of this type tends to be much less than the theoretical maximum.
This problem can be attacked by allowing different connections to share a single buffer, but this solution is not entirely satisfactory, because it fails to provide for traffic management of individual connections. A shared buffer can also be swamped by simultaneous bursts of activity on several connections. If the buffer is made large enough to prevent this, then buffer memory will be wasted because much of the buffer space will usually be unused.
Another problem with the conventional traffic shaper 400 is that it tends to waste network bandwidth resources by transmitting unnecessary idle cells. This occurs whenever the buffer scheduled for cell read-out is empty, forcing output of an idle cell, even though there are cells waiting for output in other buffers. This problem becomes increasingly serious as the number of connections increases, because the buffers that actually have cells to be output will be scheduled for output a decreasing proportion of the time.
Regardless of the number of connections, the problem of waste of bandwidth resources is aggravated when certain connections are given higher priority than others to ensure that their cells are output with minimum delay. To allow for irregularities in cell arrival times, these connections must be given extra bandwidth by scheduling their buffers for output at a higher rate than the actual rate specified in the traffic contract. This ensures, however, that the buffers will often be empty when read, forcing output of idle cells. Assigning extra bandwidth to high-priority connections also reduces the number of connections that can be handled, forcing a curtailment of the amount of service that can be provided.
Still another problem of the conventional traffic shaper 400 is that it produces uneven cell delays, because the order of output of the cells is determined by the order in which the buffers are scheduled, and not by the order in which the cells arrive. Other conditions being equal, a cell that happens to arrive Just after the scheduled time for output from its buffer will have a longer wait than a cell that happens to arrive just before the scheduled output time.
A further problem concerns the line distributors at network edge nodes. The cellstream received from the traffic shaper at one of these nodes is not tailored to the needs of the line distributor, so to distribute and frame the cellstream, the line distributor requires a large buffer in which it can temporarily store cells. It is inefficient to have large buffers in both the traffic shaper and line distributor; it would obviously be desirable to reduce the total buffer requirement.
These problems have been described in relation to an ATM network, but similar traffic-shaping problems occur in other packet communication systems: too much memory space is required for packet buffering; it is difficult to handle a very large number of connections simultaneously; and regardless of the number of connections, network bandwidth resources are not used efficiently.